package main

import (
	"fmt"
)

//输入: "babad"
//输出: "bab"
//注意: "aba"也是一个有效答案。

//输入: "cbbd"
//输出: "bb"
// 最长的回文串
func main() {
	//s := "babad"
	s := "cbabd"
	//s := "a"
	s = longestPalindrome(s)
	fmt.Println(s)
}

func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	start, len, i, s_len := 0, 1, 0, len(s)
	for i <= s_len {
		if s_len-i <= len/2 {
			break
		}
		j, k := i, i
		for k < s_len-1 && s[k] == s[k+1] {
			k++
		}
		i = k + 1
		for k < s_len-1 && j > 0 && s[j-1] == s[k+1] {
			j--
			k++
		}
		new_line := k - j + 1
		if new_line > len {
			start = j
			len = new_line
		}
	}
	return s[start : start+len]
}
func longestPalindrome2(s string) string {
	var result string
	for i := 0; i < len(s); i++ {
		for j := i + 1; j <= len(s); j++ {
			temp := string(s[i:j])
			str, flag := isPalindrome(temp)
			if flag {
				if len(str) > len(result) {
					result = str
				}
			}
		}
	}
	return result
}

func isPalindrome(s string) (string, bool) {
	//println(s)
	if len(s) == 1 || len(s) == 0 {
		return s, true
	}
	if len(s) == 2 && (s[0] == s[1] || len(s) == 3) {
		return s, true
	}

	for i, j := 0, len(s)-1; i <= j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return s, false
		}
	}

	return s, true
}
